﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Jenvin.Library.DataStruct
{
    /// <summary>
    /// 小顶堆优先队列 插入push ,pop的时间复杂度都的O(log n)
    /// pop 出来的是一个从小到大的序列
    /// SuperPriorityQueue 提供了与 PriorityQueue 不同另一种用法。
    /// 如找出所有元素的Top K.但又不想为所有的元素生成T类型的对象 插入队列 如Push(new T());
    /// 可以使用如下方法先用最小元素初始化所有队列。然后通过引用更改顶部元素
    ///     SuperPriorityQueue &lt;T &gt; queue=new SuperPriorityQueue&lt;T &gt;(Size);
    ///     T top = queue.InitializeBy(()=> return minValue of Type T);
    ///     while(i &lt; MaxElem)
    ///     {
    ///         top.SomeProperty=value;
    ///         top=queue.UpdateTop();
    ///     }
    ///     for(i=queue.Size()-1;i>=0;i++)
    ///     {
    ///        T[i]=queue.Pop()
    ///     }
    ///  当不仅仅是小顶堆，如果将Compare反序，就是大顶堆
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SuperPriorityQueue<T> : PriorityQueue<T> where T : class
    {

        /// <summary>
        /// size 为容量大小
        /// </summary>
        /// <param name="size"></param>
        public SuperPriorityQueue(int size)
            : this(size, (IComparer<T>)null)
        {

        }

        public SuperPriorityQueue(int size, Comparison<T> comparison)
            : this(size, new DelegateComparer<T>(comparison))
        {

        }
        public SuperPriorityQueue(int size, IComparer<T> comparer)
            : base(size, comparer)
        {

        }
        /// <summary>
        /// 使用minValueFunc初始化所有队列元素返回堆顶元素。
        /// </summary>
        /// <param name="minValueFunc"></param>
        /// <returns></returns>
        public T InitializeBy(Func<T> minValueFunc)
        {
            heap[1] = minValueFunc();
            for (int i = 2; i < heap.Length; i++)
            {
                heap[i] = minValueFunc();
            }
            size = heap.Length - 1;
            return Top();
        }
        /// <summary>
        /// 当你修改堆顶元素时。UpdateTop 重新调整堆。反回新的堆顶元素
        /// 只适合引用类型
        /// </summary>
        /// <returns> 
        /// </returns>
        public T UpdateTop()
        {
            DownHeap();
            return heap[1];
        }
    }
}
